package style.Leetcode.初级算法.linkedList.linkedList_20220816_3_反转链表;

import style.Leetcode.初级算法.linkedList.ListNode;

import java.util.Stack;

/**
 * 给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。
 *
 * 输入：head = [1,2,3,4,5]
 * 输出：[5,4,3,2,1]
 *
 * 输入：head = [1,2]
 * 输出：[2,1]
 *
 * 输入：head = []
 * 输出：[]
 *
 *
 */
public class Solution {
    /**
     * 思路一：栈   后进先出
     */
    public ListNode reverseList1(ListNode head) {
        Stack<ListNode> stack = new Stack<>();
        // 链表全部入栈
        while (head != null) {
            stack.push(head);
            head = head.next;
        }

        if (stack.isEmpty()) return null;

        ListNode node = stack.pop();
        ListNode dumy = node;
        // 栈中结点全部出栈，然后重新连成新的链表
        while (!stack.isEmpty()) {
            ListNode tempNode = stack.pop();
            node.next = tempNode;
            node = node.next;
        }

        // 最后一个结点就是反转前的头结点，一定要让他的next等于空，否则构成环
        node.next = null;
        return dumy;
    }


    /**
     * 思路二：双指针  头插法
     */
    public ListNode reverseList2(ListNode head) {
        ListNode newHead = null;
        while (head != null) {
            //先保存访问的节点的下一个节点，保存起来
            //留着下一步访问的
            ListNode temp = head.next;
            //每次访问的原链表节点都会成为新链表的头结点，
            //其实就是把新链表挂到访问的原链表节点的
            //后面就行了
            head.next = newHead;
            //更新新链表
            newHead = head;
            //重新赋值，继续访问
            head = temp;
        }
        //返回新链表
        return newHead;
    }

    /**
     * 重点思路三：迭代反转 next 指针
     *      1、两个指针同时往后移动，next指针做变化
     */
    public ListNode reverseList3(ListNode head) {
        ListNode prev = null;
        ListNode curr = head;
        while (curr != null) {
            ListNode next = curr.next;
            curr.next = prev;
            prev = curr;
            curr = next;
        }
        return prev;
    }




    public static void main(String[] args) {
        Solution solution = new Solution();
        ListNode head = new ListNode(1);
        head.next = new ListNode(2);
        head.next.next = new ListNode(3);
        head.next.next.next = new ListNode(4);
        head.next.next.next.next = new ListNode(5);
        head.next.next.next.next.next = new ListNode(6);
//        ListNode listNode1 = solution.reverseList1(head);
//        ListNode listNode2 = solution.reverseList2(head);
        ListNode listNode3 = solution.reverseList3(head);
        System.out.println(listNode3);

    }
}
